package com.algorithm.knapsack;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Random;

import com.problem.knapsack.KPProblem;
import com.util.random.RandomGenerator;
import com.util.solution.impl.KPSolution;
import com.util.solution.inter.KDNode;

public class ParetoLocalSearch {
	private KPProblem problem;
	private int run_num;
	public ParetoLocalSearch(KPProblem problem, int run_num){
		this.problem = problem;
		this.run_num = run_num;
	}
	public void execute(int iteration){
		long startMili=System.currentTimeMillis();
		Iterator<KDNode<KPSolution>> iter = problem.kdSet.getKDNodes().iterator();		
		while(iter.hasNext()){
			KDNode<KPSolution> t = iter.next();
			try {
				this.problem.kdStartingSet.add(t.solution.clone());
			} catch (CloneNotSupportedException e) {
				e.printStackTrace();
			}
		}
		while(true){
			int remain = this.problem.kdStartingSet.getPopSize();
			if(remain==0) break;
			this.PLSexecute();
			problem.kdSet.clearAndReset();
		}
		long endMili=System.currentTimeMillis();
		System.out.println("Run of "+this.run_num+":"+(endMili-startMili)/1000+" s ");
		problem.kdSet.saveObjectiveResults("files/results/kp/"+problem.problem_des+problem.item_num+"-"+problem.obj_num+"_"+run_num+".txt");
	}
	public void PLSexecute(){
		int size = problem.kdStartingSet.getPopSize();
		if(size==0) return;
		Random rand = new Random();
		int index = rand.nextInt(size);
		KDNode<KPSolution> s = problem.kdStartingSet.getKDNodes().get(index);
		this.generateNeighborhood(s.solution);
		s.isDominated = true;
		this.problem.kdStartingSet.clearAndReset();
	}
	/**
	 * generate the neighborhood of s
	 * @param s
	 */
	public void generateNeighborhood(KPSolution s){
		ArrayList<Integer> selectSet = new ArrayList<>();
		ArrayList<Integer> unSelectSet = new ArrayList<>();
		for(int i=0;i<this.problem.item_num;i++){
			if(s.item_array[i]==1){
				selectSet.add(i);
			}else{
				unSelectSet.add(i);
			}
		}
		int len1 = selectSet.size();
		int len2 = unSelectSet.size();
		int loop = 2;
		int opt = 2;
		for(int i=0;i<loop;i++){
			int [] rand_array = RandomGenerator.permutation_array(0, len1-1);
			for(int j = 0;j <= len1-opt;j+=opt){
				for(int x = 0;x < len2;x++){
					try {
						KPSolution temp = s.clone();
						for(int k=0;k<opt;k++){
							int pos = selectSet.get(rand_array[j+k]);
							temp.item_array[pos] = 0;
							for(int m=0;m<problem.obj_num;m++){
								temp.object_val[m] -= this.problem.profitArray[m*problem.item_num+pos];
								temp.current_weight[m] -= this.problem.weightArray[m*problem.item_num+pos];
							}
						}
						boolean canAdd = false;
						int betterTimes = 0;
						for(int y=x;y<len2;y++){
							int chosePos = unSelectSet.get(y);
							boolean isValid = true;
							for(int n=0;n<problem.obj_num;n++){
								int tempWeight = temp.current_weight[n] + this.problem.weightArray[n*problem.item_num+chosePos];
								if(tempWeight > this.problem.capacityArray[n]){
									isValid = false;
									break;
								}
							}
							if(isValid){
								canAdd = true;
								temp.item_array[chosePos] = 1;
								for(int n=0;n<problem.obj_num;n++){
									temp.object_val[n] += this.problem.profitArray[n*problem.item_num+chosePos];
									if(temp.object_val[n] > s.object_val[n]){
										betterTimes++;
									}
									temp.current_weight[n] += this.problem.weightArray[n*problem.item_num+chosePos];
								}
							}
						}
						if(canAdd && betterTimes > 0){
							if(this.problem.kdSet.add(temp)){
								this.problem.kdStartingSet.add(temp);
							}
						}
					} catch (CloneNotSupportedException e) {
						e.printStackTrace();
					}
				}
			}
		}
	}
	public static void main(String []args){
		for(int i=0;i<20;i++){
			KPProblem kp = new KPProblem("kp");
			new ParetoLocalSearch(kp, i).execute(0);
		}
	}
}
